package ljl.codetop300;

/**
 * 虽然说我的笨逼解法看着笨逼，但是目前我认为我的好理解
 * 那两个解法我看了一遍没看懂
 */
public class _45_jump_2 {

  /**
   * 我的笨逼解法
   */
  static class min_stupid_cunt_solution {
    public int jump(int[] nums) {
      // 表示最少几步能过来；到当前位置了，更新后面能到的所有位置：是 min(自己+1，对方的）
      int[] dp = new int[nums.length];
      for (int i = 1; i < nums.length; i++) {
        dp[i] = nums.length;
      }
      for (int i = 0; i < nums.length; i++) {
        for (int j = 1; j <= nums[i]; j++) {
          int next = Math.min(nums.length, i + j);
          dp[next] = Math.min(dp[next], dp[i] + 1);
        }
      }
      return dp[nums.length - 1];
    }
  }

  /**
   * 结果确实是对的，但是理由？为什么是对的？
   * 确实，前面的不可能跳过最大的那个位置导致最终多了几步，所以前面的只要能到达最多的那个就行
   * 反正不知道为什么，就是对的
   */
  static class s1 {
    public int jump(int[] nums) {
      int position = nums.length - 1;
      int steps = 0;
      while (position > 0) {
        for (int i = 0; i < position; i++) {
          if (i + nums[i] >= position) {
            position = i;
            steps++;
            break;
          }
        }
      }
      return steps;
    }
  }

  static class s1_copy {

    public int jump(int[] nums) {
      int step = 0;
      int farthest = nums.length - 1;
      while (farthest > 0) {
        for (int i = 0; i < farthest; i++) {
          if (i + nums[i] >= farthest) {
            step++;
            farthest = i;
            break;
          }
        }
      }
      /*
       我还说人家的循环奇怪，你看看我这个修改之后的不奇怪的循环，是不是更奇怪？
       神经病啊！

       for (int i = 0; farthest > 0 && i < farthest; i++) {
         if (i + nums[i] >= farthest) {
           step++;
           farthest = i;
           i = -1;
         }
       }
      */
      return step;
    }
  }

  /**
   * 一轮一轮的来：
   * 一上来二话不说先来一步，记录一下这一步最远能到哪
   * 然后到这个最远距离之前（含），每一步都更新下一次最远能到哪
   * 然后走完当前步骤，看看是不是到了上一次的最远距离了，如果到了，得加一步了
   * 因为你不可能一步走到这一步的最远距离，所以加一是必须的
   * 最后一步不能判断。因为上一步能到的距离肯定能到最后一步。可能会导致多一步。
   */
  static class s2 {
    public int jump(int[] nums) {
      int length = nums.length;
      int end = 0;
      int maxPosition = 0;
      int steps = 0;
      for (int i = 0; i < length - 1; i++) {
        maxPosition = Math.max(maxPosition, i + nums[i]);
        if (i == end) {
          end = maxPosition;
          steps++;
        }
      }
      return steps;
    }
  }

  static class copy_s2 {

    /**
     * 思路：结果是 step，记录每一轮最远能到哪，然后如果到达最远处时，step+1
     * 返回 step
     */
    public int jump(int[] nums) {
      int farthest = 0;
      int step = 0;
      int border = 0;
      for (int i = 0; i < nums.length - 1; i++) {
        farthest = Math.max(i + nums[i], farthest);
        if (i == border) {
          step++;
          border = farthest;
        }
      }
      return step;
    }
  }

}
